public class InfixPostfix
{

	public static void main(String[] args)
	{
		String infix = "9+5*6-9/8+9*6*5-5/5/4+9";
		
		System.out.println("Infix:\t\t" + 		"4+5*6-9/8+9*6*5-5/5/4+9");
		System.out.println("Postfix:\t" + 		inToPost(infix));			//456*+98/-96*5*+55/4/-9+
		System.out.println("Tekrar infix:\t"+ 	postToIn(inToPost(infix)));	//(((((4+(5*6))-(9/8))+((9*6)*5))-((5/5)/4))+9)
		System.out.println("Sonuc:\t\t"+	 	postToValue(inToPost(postToIn(inToPost(infix)))));	//311.625
		
	}
	
	public static String inToPost(String infix)
	{
		Stack a = new Stack();
		String postfix = "";

		for(int i = 0; i < infix.length(); i++)
		{
			if(Character.isDigit(infix.charAt(i)))
				postfix += Character.toString(infix.charAt(i));

			else if(infix.charAt(i) == '(')
			{
				int acParantezPos = i;
				int acikParantez = 1;
				i++;
				
				for(;acikParantez != 0;i++)
				{
					if(infix.charAt(i) == '(')
						acikParantez++;
					if(infix.charAt(i) == ')')
						acikParantez--;
				}
				i--;	//-1 son donen for'un geri alinisi
				postfix += inToPost(infix.substring(acParantezPos+1, i));	//+1 '(' almamasi icin.
			}
			
			else
			{
				if(infix.charAt(i) == '+' || infix.charAt(i) == '-')
				{
					while(!a.isEmpty())
						postfix += a.pop();
				
					a.push(Character.toString(infix.charAt(i)));
				}

				if(infix.charAt(i) == '*' || infix.charAt(i) == '/')
				{
					if(a.top().charAt(0) == '*' || a.top().charAt(0) == '/')
						postfix += a.pop();

					if((!a.isEmpty()) && (a.top().charAt(0) == '+' || a.top().charAt(0) == '-'))
						a.push(Character.toString(infix.charAt(i)));
					else	//	(a.isEmpty()) || (a.top().charAt(0) != '+' && a.top().charAt(0) != '-')
						a.push(Character.toString(infix.charAt(i)));

				}
			}	
		}
		while(!a.isEmpty())
			postfix += a.pop();
		
		return postfix;
	}

	public static String postToIn(String postfix)
	{
		Stack a = new Stack();
		String temp;

		for(int i = 0; i < postfix.length(); i++)
		{
			if(Character.isDigit(postfix.charAt(i)))
				a.push(Character.toString(postfix.charAt(i)));
			else
			{
				temp = a.pop();
				a.push("(" + a.pop() + postfix.charAt(i) + temp + ")");
			}	
		}
		
		return a.pop();
	}

	public static String postToValue(String postfix)
	{
		Stack a = new Stack();
		double temp;
		for(int i = 0; i < postfix.length(); i++)
		{
			if(Character.isDigit(postfix.charAt(i)))
				a.push(Character.toString(postfix.charAt(i)));
			else
				switch(postfix.charAt(i))
				{
				case '+':
					temp = Double.parseDouble(a.pop()) + Double.parseDouble(a.pop());
					a.push(Double.toString(temp));
					break;
				case '-':
					temp = Double.parseDouble(a.pop()) - Double.parseDouble(a.pop());
					temp = -temp;	//ilk cekilen 2. deger
					a.push(Double.toString(temp));
					break;
				case '*':
					temp = Double.parseDouble(a.pop()) * Double.parseDouble(a.pop());
					a.push(Double.toString(temp));
					break;
				case '/':
					temp = Double.parseDouble(a.pop()) / Double.parseDouble(a.pop());
					temp = 1.0 / temp;	//ilk cekilen deger 2. deger
					a.push(Double.toString(temp));
					break;
				}
		}
			return a.pop();
	}
	
}

class Stack
{
	StackType son = null;
	
	public void push(String it)
	{
		StackType a = new StackType();
		a.pre = son;
		a.data = it;
		
		son = a;
	}
	
	public String pop()
	{
		if(!(son == null))
		{
			String temp = son.data;
			son = son.pre;		//java'da dispose() otomatik gerceklesir.
			return temp;
		}
		else
		{
			System.out.println("stack bos!");
			return "";
		}
	}
	
	public String top()
	{
		if(son != null)
			return son.data;
		else
			return " ";
	}
	
	public boolean isEmpty()
	{
		return (son == null ? true : false);
	}
}

class StackType
{
	StackType pre;
	public String data;
}

